//
// Created by 123 on 2024/3/25.
//
/**
 * 每次输入入度为0的点，
 * 并将各个点的入度减一
 */
#include <iostream>
#include <vector>
#include <stack>
#include "../../6_树/并查集/union_look_up_set.cpp"

using namespace std;
#define VexNum 5
typedef struct Edge {
//    弧尾
    int r;
//    弧头
    int h;
//    权值
    int data;
//    是否加入树中
    bool flag;
} Edge;

typedef struct Graph {
    Edge *edges[1000];
    int size = 0;
} Graph;

//下标对应点的信息
string vex[VexNum] = {"V1", "V2", "V3", "V4", "V5"};
int weight[VexNum] = {0, 0, 0, 0, 0,};


//获得边，其实就是初始化一个边
Edge *getEdge(int r, int h, int data);

//添加边，网图中添加边集
void addEdge(Graph &graph, Edge *edge);

//获取下一个临接的点集的下标
vector<int> getNextNode(Graph graph, int vex);

//初始化数据
void init(Graph &graph);


//拓扑排序
void Topological_Sort(Graph graph) {
    stack<int> sta;
    int count = 0;
    for (int i = 0; i < VexNum; ++i) {
        if (weight[i] == 0)
            sta.push(i);
    }
    while (!sta.empty()) {
        int index = sta.top();
        sta.pop();
        cout << vex[index] << "   ";
        count++;
        vector<int> arr = getNextNode(graph, index);
        for (int i = 0; i < arr.size(); ++i) {
            int we = weight[arr[i]] - 1;
            weight[arr[i]] = we;
            if (we == 0)
                sta.push(arr[i]);
        }
    }
    cout<<endl;

    if(count<VexNum){
        cout<<"ERROR!";
    }else{
        cout<<"RIGHT!";
    }
    cout<<endl;
}


int main() {
    Graph graph;
    init(graph);
    Topological_Sort(graph);

}


vector<int> getNextNode(Graph graph, int vex) {
    vector<int> arr;
    for (int i = 0; i < graph.size; ++i) {
        if (vex == graph.edges[i]->r) {
            arr.push_back(graph.edges[i]->h);
        }
    }
    return arr;
}

void init(Graph &graph) {

    addEdge(graph, getEdge(0, 1, 6));
    addEdge(graph, getEdge(0, 3, 6));
    addEdge(graph, getEdge(1, 2, 6));
    addEdge(graph, getEdge(1, 3, 6));
    addEdge(graph, getEdge(2, 4, 6));
    addEdge(graph, getEdge(3, 2, 6));
    addEdge(graph, getEdge(3, 4, 6));

//    添加入度信息
    for (int i = 0; i < graph.size; ++i) {
        weight[graph.edges[i]->h] = weight[graph.edges[i]->h] + 1;
    }
}

void addEdge(Graph &graph, Edge *edge) {
    graph.edges[graph.size++] = edge;
}

Edge *getEdge(int r, int h, int data) {
    Edge *e = (Edge *) malloc(sizeof(Edge));
    e->data = data;
    e->h = h;
    e->r = r;
    e->flag = false;
    return e;
}

